package com.leetcode.dfs;

import java.util.ArrayList;
import java.util.List;

public class KNCombine {
    public static void main(String[] args) {

    }

    List<List<Integer>> resList = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(new ArrayList<>(), n, k, 1);
        return resList;
    }

    private void dfs(List<Integer> tmpList, int n, int k, int curInd) {
        if (tmpList.size() + (n - curInd + 1) < k) {
            return;
        }
        if (tmpList.size() == k) {
            resList.add(new ArrayList<>(tmpList));
            return;
        }
        tmpList.add(curInd);
        dfs(tmpList, n, k, curInd+1);
        tmpList.remove(tmpList.size() - 1);
        dfs(tmpList, n, k, curInd + 1);

    }
}
